package datastructure.queue03;


import org.junit.jupiter.api.Test;

/**
 * 队列操作
 *
 * @Filename: QueueTest
 * @Author: czh
 * @Data:2023/1/3 11:41
 * <p>
 * 顺序队列和链式队列
 * 先进先出
 */
public class QueueTest {
    /**
     * 测试数组队列
     */
    @Test
    public void testArrayQueue() {
        ArrayQueue arrayQueue = new ArrayQueue(4);
        arrayQueue.offer("A");
        arrayQueue.offer("B");
        arrayQueue.offer("C");
        arrayQueue.poll();
        arrayQueue.display();
        arrayQueue.offer("D");
        arrayQueue.display();
    }

    /**
     * 测试链表队列
     */
    @Test
    public void testLinkQueue() {
        LinkQuery linkQuery = new LinkQuery();
        linkQuery.offer("A");
        linkQuery.offer("B");
        linkQuery.offer("C");
        System.out.println(linkQuery.peek());  // A
        linkQuery.poll();
        System.out.println(linkQuery.peek());   // B
        linkQuery.poll();
        linkQuery.offer("D");
        System.out.println(linkQuery.peek());   // C
    }
}

/**
 * 数组环形队列
 */
class ArrayQueue<T> {
    private int maxSize; //队列长度，由构造函数初始化 
    private T[] queArray; // 队列
    private int front; //队头
    private int rear; //队尾

    // 初始化构造器
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queArray = (T[]) new Object[maxSize];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 判断队列是否为满
     *
     * @return
     */
    public boolean isFull() {
        return (this.rear + 1) % this.maxSize == this.front;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return this.rear == this.front;
    }

    /**
     * 入队操作
     *
     * @param value
     */
    public void offer(T value) {

        if (isFull()) {
            System.out.println("队列已满");
        } else {
            this.queArray[rear] = value;
            rear = (rear + 1) % maxSize;
        }
    }

    /**
     * 出队列操作
     */
    public T poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        } else {
            T t = queArray[front];
            front = (front + 1) % maxSize;
            return t;
        }
    }

    /**
     * 获取队列头
     */
    public void peek() {
        System.out.println(this.queArray[this.front]);
    }

    /**
     * 获取有效元素的个数
     */
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 遍历有效的队列
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("队列为空");
        }
        for (int i = this.front; i < front + size(); i++) {
            System.out.printf(" " + queArray[i % maxSize]);
        }
        System.out.println();
    }
}


/**
 * 链表队列
 */
class LinkQuery {
    Node3 firstNode; // 队头
    Node3 lastNode; // 队尾

    /**
     * 判断队列为空
     */
    public boolean isEmpty() {
        return this.firstNode == null;
    }

    /**
     * 入队(尾插法)
     *
     * @param data
     */
    public void offer(Object data) {
        Node3 current = new Node3(data);
        if (this.firstNode == null) {
            this.firstNode = current;
            this.lastNode = current;
        } else {
            this.lastNode.next = current;
            this.lastNode = current;
        }
    }

    /**
     * 出队
     */
    public Object poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        Object data = this.firstNode.data;
        this.firstNode = this.firstNode.next;
        return data;
    }

    /**
     * 获取队列头
     */
    public Object peek() {
        return this.firstNode.data;
    }

}

class Node3 {
    public Object data;
    public Node3 next;

    public Node3(Object object) {
        this.data = object;
    }
}